package com.duneyr.snakes.generate;

import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;

import com.duneyr.snakes.Level;
import com.duneyr.snakes.generate.GenBlock.Type;
import java.util.ArrayList;

public abstract class AbstractGenMap implements GenMap {

    protected List<GenRoom> rooms;
    protected Set<GenCorridor> corridors;
    protected GenBlock[][] map;
    Node[][] nodes;

    public AbstractGenMap(int width, int height) {
        rooms = new ArrayList<GenRoom>();
        corridors = new HashSet<GenCorridor>();
        initializeMap(width, height);
    }
    
    private void initializeMap(int width, int height) {
        map = new GenBlock[width][height];
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                map[x][y] = new GenBlock(Type.EMPTY);
            }
        }
    }
    
    /**
     * Attempts to place a Large room. A large room may consist of two or more
     * (joined) rectangles. Will retry up to 5 times if the room overlaps other
     * rooms, before stopping.
     * 
     * @param random
     *            for random numbers
     */
    public void addRandomLargeRoom(Random random) {
        addRandomLargeRoom(random, 5);
    }

    /**
     * Attempts to place a Large room. A large room may consist of two or more
     * (joined) rectangles.
     * 
     * @param random
     *            for random numbers
     * @param nRetry
     *            if the random room overlaps, how many times should this method
     *            retry at placing a room? before stopping
     */
    public void addRandomLargeRoom(Random random, int nRetry) {
        // TODO impl.
    }

    /**
     * Add a simple rectangular room. Will retry up to 5 times.
     * 
     * @param random
     *            for random numbers
     */
    public void addRandomRoom(Random random) {
        addRandomRoom(random, 5);
    }

    /**
     * Add a simple rectangular room. Will retry up to nRetry times.
     * 
     * @param random
     *            for random numbers
     * @param nRetry
     *            the maximum numbers of retries.
     */
    public void addRandomRoom(Random random, int nRetry) {
        while (nRetry-- > 0) {
            // get a random rectangle
            int x = random.nextInt(width());
            int y = random.nextInt(height());
            int w = random.nextInt(4) + 2;
            int h = random.nextInt(4) + 2;
            
            if (checkValid(x, y, w, h)) {
                applyRoom(x, y, w, h);
                return;
            }
        }
    }

    /**
     * Make all block in the rooms area into room tiles and make sure to clear
     * all walls, and all doors on the inside of the room, and make walls around
     * the outside.
     */
    private void applyRoom(int x0, int y0, int w, int h) {
        GenRoom room = new GenRoom();
        rooms.add(room);

        int x1 = x0 + w;
        int y1 = y0 + h;
        for (int x = x0; x < x1; x++) {
            for (int y = y0; y < y1; y++) {
                GenBlock block = map[x][y];
                block.clearAllWalls();
                if (block.type != GenBlock.Type.STAIRS) {
                    block.setType(room);
                }
                GenPosition p = new GenPosition(x, y);

                setWallIfEqual(x0, x, block, GenBlock.WALL, GenBlock.WEST, room, p);
                setWallIfEqual(x1-1, x, block, GenBlock.WALL, GenBlock.EAST, room, p);
                setWallIfEqual(y0, y, block, GenBlock.WALL, GenBlock.NORTH, room, p);
                setWallIfEqual(y1-1, y, block, GenBlock.WALL, GenBlock.SOUTH, room, p);
            }
        }
    }

    private static void setWallIfEqual(int a, int b, GenBlock block,
            byte kind, byte directions, GenRoom room, GenPosition p) {
        if (b == a) {
            block.setWall(kind, directions);
            room.addPerimeterBlockPosition(p);
        }
    }

    private boolean checkValid(int x0, int y0, int w, int h) {
        int x1 = x0 + w;
        int y1 = y0 + h;
        //Bound checking
        if (x0 >= x1 || x1 >= width() || y0 >= y1 || y1 >= height()) {
            return false;
        }
        //Collision checking
        for (int x = x0; x < x1; x++) {
            for (int y = y0; y < y1; y++) {
                GenBlock block = map[x][y];
                if (block.type == Type.ROOM || block.type == Type.CORRIDOR) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Connects the two rooms r1 and r2 if not already connected by a corridor.
     * If room r2 is already connected to r3 when the connection r1-r2 has been
     * made, r3 is considered to be connected to r1 and r1 to r3, thus a call
     * connect(r1,r3) could do nothing. (But it may add a direct connection
     * r1-r3 if possible). Will attempt to connect through other rooms if
     * necessary.
     * 
     * @param r1
     *            room one.
     * @param r2
     *            room two.
     */
    public void connect(GenRoom r1, GenRoom r2) {
        initializeNodes();

        // First a simple connectivity check:
        if (r1.isConnectedTo(r2)) {
            return;
        }
        //Then try using A*
        GenPosition point1 = r1.connectionPoint(r2, this);
        GenPosition point2 = r2.connectionPoint(r1, this);

        Node A = nodes[point1.x][point1.y];
        Node B = nodes[point2.x][point2.y];

        Queue<Node> open = new PriorityQueue<Node>();
        Queue<Node> closed = new PriorityQueue<Node>();

        open.add(A);

        while (!open.isEmpty()) {
            Node current = open.poll();

            if (current.equals(B) || current.isConnectedTo(r2)) {
                makeConnection(current);
                return;
            }

            closed.add(current);

            /* foreach neighbor */
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == dy || dx == -dy) {
                        continue;
                    }
                    int mx = current.x + dx;
                    int my = current.y + dy;
                    if(mx < 0 || mx >= width() || my < 0 || my >= height()){
                    	continue;
                    }
                    
                    Node m = nodes[mx][my];

                    if (closed.contains(m)) {
                        continue;
                    }
                    float g = current.g + m.cost();
                    if (m.g > g) {
                        open.remove(m);
                    }
                    if (!open.contains(m)) {
                        m.prev = current;
                        m.g = g;
                        m.calculateH(B.x, B.y);
                        open.add(m);
                    }
                }
            }

        }
        // if we get here we could not find a way which is unlikely
        // because no positions are completely blocked just simply
        // more more resistive.
        throw new RuntimeException("Corridor Generation Failed");
    }

    /**
     * Get one of the rooms on this map.
     * 
     * @return a room.
     */
    public GenRoom getRandomRoom(Random random) {
        final int size = rooms.size();
        System.out.println("Size:" + size);
        return rooms.get(random.nextInt(size));
    }

    public int height() {
        return map[0].length;
    }

    private void crossConnect(Set<GenRoom> roomsThatConnect, Set<GenCorridor> connectedCorridors) {
        for (GenRoom room : roomsThatConnect) {
            room.connectTo(roomsThatConnect);
        }
        for (GenCorridor corridor: connectedCorridors){
            corridor.connectTo(roomsThatConnect);
        }
    }

    private void initializeNodes() {
        if (nodes == null) {
            nodes = new Node[width()][height()];
            for (int x = 0; x < width(); x++) {
                for (int y = 0; y < height(); y++) {
                    nodes[x][y] = new Node(x, y);
                }
            }
        } else {
            // reset g for the nodes
            for (Node[] collumn : nodes) {
                for (Node node : collumn) {
                    node.reset();
                }
            }
        }
    }

    /**
     * Make a connection between rooms using the backlinks in c.
     * 
     * @param c the last node in the path
     */
    private void makeConnection(Node c) {
        Set<GenRoom> roomsThatConnect = new HashSet<GenRoom>();
        Set<GenCorridor> connectedCorridors = new HashSet<GenCorridor>();
        GenCorridor corridor = new GenCorridor();
        
        connectedCorridors.add(corridor);
        //first treat c it self specially.

        while (c.prev != null) {
            makeConnection(c.prev, roomsThatConnect, connectedCorridors, corridor);
            fixWallsToConnectBlocks(c);
            c = c.prev;
        }
        crossConnect(roomsThatConnect, connectedCorridors);
    }
    
    private void fixWallsToConnectBlocks(Node next) {
    	Node c = next.prev;
    	byte dirCN = c.getDirection(next);
    	byte dirNC = next.getDirection(c);
    	c.getBlock().eraseWall(GenBlock.WALL_DOOR, dirCN);
    	next.getBlock().eraseWall(GenBlock.WALL_DOOR, dirNC);
    } 
 
    private void makeConnection(Node n, Set<GenRoom> cRooms, Set<GenCorridor> cCorridors, GenCorridor c) {
        final GenBlock block = n.getBlock();
        final Type t = block.type;
        if (t.equals(Type.ROOM)) {
            cRooms.add(block.room);
        } else if (t.equals(Type.CORRIDOR)) {
            cRooms.addAll(block.corridor.getConnectedRooms());
            cCorridors.add(c);
        } else if (t.equals(Type.EMPTY)) {
            block.setType(c);
            block.setWall(GenBlock.ALLWALLS, GenBlock.NONE);
            corridors.add(c);
        }
    }

    /**
     * Fill empty areas next to corridors with small rooms.
     */
    public void roomFill() {
        // TODO impl.
    }

    /**
     * Returns an collection or array or Iterable of some sort that allows for
     * iteration of all the rooms
     * 
     * @return Iterable covering all the rooms
     */
    public Iterable<GenRoom> rooms() {
        return rooms;
    }

    /**
     * Turn into a level object.
     * 
     * @return
     */
    public Level toLevel() {
        //TODO impl.
        throw new UnsupportedOperationException();
    }

    public int width() {
        return map.length;
    }
    
   

    protected class Node implements Comparable<Node> {

        float g = -1;
        float h = -1;
        Node prev;
        int x, y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        //Only needs to work for neighboring nodes
        public byte getDirection(Node next) {
        	int dx = next.x-x;
        	int dy = next.y-y;
        	if(dx == 0){
        		return (dy > 0)?GenBlock.SOUTH:GenBlock.NORTH;
        	}
        	if(dy == 0){
        		return (dx > 0)?GenBlock.EAST:GenBlock.WEST;
        	}
			return GenBlock.EAST;
		}

		@Override
        public int compareTo(Node o) {
            return (int) Math.signum(f() - o.f());
        }

        float cost() {
            return getBlock().type.getCost();
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            Node other = (Node) obj;
            if (!getOuterType().equals(other.getOuterType())) {
                return false;
            }
            if (x != other.x) {
                return false;
            }
            if (y != other.y) {
                return false;
            }
            return true;
        }

        float f() {
            return h + g;
        }

        GenBlock getBlock() {
            return map[x][y];
        }

        private AbstractGenMap getOuterType() {
            return AbstractGenMap.this;
        }

        protected void calculateH(int x, int y) {
            //h = (float) Math.hypot(x - this.x, y - this.y);
        	h = Math.abs(x-this.x) + Math.abs(y-this.y);
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + getOuterType().hashCode();
            result = prime * result + x;
            result = prime * result + y;
            return result;
        }

        /**
         * return true if and only if this is a node representing a corridor block and
         * the corridor object in corridors that contains the block that this node
         * represents is connected to r2
         * 
         * @param room
         *            a room to aim for
         * @return true or false
         */
        public boolean isConnectedTo(GenRoom room) {
            GenBlock block = getBlock();
            Type type = block.type;
            if (type.equals(GenBlock.Type.ROOM)) {
                return block.room.isConnectedTo(room);
            } else if (type.equals(GenBlock.Type.CORRIDOR)) {
                return block.corridor.connectsTo(room);
            }
            return false;
        }

        public void reset() {
            g = -1;
            h = -1;
            prev = null;
        }
    }
}